package linkedList;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 限制
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 */
public class MergeKSortedList_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        // 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征，基于堆实现。
        Queue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val-b.val));

        // 将 k 个链表的头结点加入最小堆
        for (ListNode list : lists) {
            pq.add(list);
        }

        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            head.next = node;
            // 各链表的头结点已经加入过了，因此需要next
            node = node.next;
            if (node != null) {
                pq.add(node);
            }
            head = head.next;
        }
        return dummy.next;
    }
}
